Subdev 分享 | Substrate Runtime 中的堆排序

作者: 周洋，《 Substrate快速入门与开发实战》开发课第三期助教。某区块链项目核心开发者，拥有多年的汽车电子嵌入式开发及区块链开发经验，擅长 C++，Go，Rust 语言。

《Substrate 快速入门与开发实战》 是一块链习联合 Laminar CTO 、Substrate、Polkadot 贡献代码者、 Polkadot 社区大使陈锡亮老师共同打造的全球第一门 Substrate 开发实战指南课程。

目前第三期课程已经进行到第四周，我们希望通过这门精心打磨的课程，在这一年内为全球区块链行业培养 200 位最顶尖的 Substrate 开发者。

每周日晚 8 点，都会进行《Substrate 快速入门与开发实战》开发课的内容知识拓展——助教技术分享会。昨晚，由周洋助教给我们带来「助教技术分享会」第 3讲，题为「Substrate Runtime 中的堆排序」。

 以下为周洋助教分享的复盘内容。

1.给加密猫

添加一个 lifetime 属性

在第一期课程的挑战赛中，我们小组为加密猫添加了 lifetime 属性。lifetime 可以理解为小猫的寿命，如果一只猫存在的时间达到了生命周期，它对应的 token 会被系统自动删除掉，这只猫也消失了。

要求链上自动化完成上述过程，所以每次 import block 都要检查哪些猫的 lifetime 超时需要被删除。由于所有猫被存在一个数组结构中，找出 lifetime 超时的猫是典型的寻找 Top K 问题。

如果实现不当，可能会引入 O(n) 的时间复杂度，进而有可能发生对链的恶意攻击。这时使用堆排序可以将时间复杂度降低为O(nlogn)。

今天分享主要关注 heap 的实现，不会有加密猫 lifetime feature 实现细节。

2. 堆排序介绍

 堆需要以下2个条件：

1. 堆是一个完全二叉树；

2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

堆排序有几个非常重要的应用：优先级队列、求 Top K 和 求中位数。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

rust 标准库里面提供了 binary heap 的实现，但是现在我们还不能在 Substrate Runtime 环境下直接使用它。

那么我们在 Substrate Runtime 环境中实现一个泛型的堆结构，并且利用 Substrate 默认的 storage value 作为堆的存储来解决 Top K 问题。

3.要实现一个堆，

我们先要知道如何存储一个堆

用数组来存储完全二叉树是个不错的选择。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，非常节省存储空间。

先来看一下这个堆结构代码的样子：

这里 T 代表堆中元素类型。C 代表 Compare trait，可供自定义排序方式（决定是大顶堆还是小顶堆）。S 代表存储类型，这个数组利用了 Substrate 提供的 StorageValue<Vec<T>, Query=Vec<T>> 类型。

我画了一个用数组存储堆的例子:

从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2+1 的节点，右子节点就是下标为 i∗2+2 的节点。

 寻找左子节点，右子节点对应的代码：

 寻找父节点对应代码：

4. 下面看一看堆的基本操作

 向堆中 push 一个元素：

往堆中插入一个元素后，我们需要进行调整，让其重新满足堆的特性，这个过程叫作堆化（heapify）。

堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。我这里画了一张堆化的过程分解图。

我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。

 对应的代码：

通过简单的递归实现向上交换。

 pop 堆顶元素：

 对应代码：

 单元测试如何使用的这个堆结构：

以上代码可以参考这里

https://github.com/yz89/substrate-heap/blob/master/runtime/src/heap.rs 

有完整的实现及单元测试。

总结一下。我们实现了一个泛型的堆结构，用户可以自定义元素类型及排序方式（大顶堆，小顶堆）。使用了Substrate 内置的 StorageValue 作为堆的存储，这样为 Substrate Runtime 提供了通用的堆排序实现。

更多阅读：

扫码关注公众号，回复“1”加入开发者社群